package bin_tree;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 基础二叉树实现
 * 使用左右孩子表示法
 **/
public class MyBinTree {
    private static class TreeNode {
        char val;
        // 左子树根节点
        TreeNode left;
        // 右子树的根节点
        TreeNode right;
        public TreeNode(char val) {
            this.val = val;
        }
    }

    /**
     * 创建一个二叉树，返回根节点
     * @return
     */
    public static TreeNode build() {
        TreeNode nodeA = new TreeNode('A');
        TreeNode nodeB = new TreeNode('B');
        TreeNode nodeC = new TreeNode('C');
        TreeNode nodeD = new TreeNode('D');
        TreeNode nodeE = new TreeNode('E');
        TreeNode nodeF = new TreeNode('F');
        TreeNode nodeG = new TreeNode('G');
        TreeNode nodeH = new TreeNode('H');
        nodeA.left = nodeB;
        nodeA.right = nodeC;
        nodeB.left = nodeD;
        nodeB.right = nodeE;
        nodeE.right = nodeH;
        nodeC.left = nodeF;
        nodeC.right = nodeG;
        return nodeA;
    }

    /**
     * 先序遍历 : 根左右
     * 传入一颗二叉树的根节点，就可以按照先序遍历的方式来输出节点值
     * @param root
     */
    public static void preOrder(TreeNode root) {
        // 边界条件
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        // 按照先序遍历的方式递归访问左树
        preOrder(root.left);
        // 按照先序遍历的方式递归访问右树
        preOrder(root.right);
    }

    /**
     * 中序遍历
     * 传入一棵二叉树的根节点，就能按照中序遍历的方式来输出结果集
     * @param root
     */
    public static void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        // 先递归访问左子树
        inOrder(root.left);
        System.out.print(root.val + " ");
        // 最后递归访问右子树
        inOrder(root.right);
    }

    /**
     * 后序遍历
     * @param root
     */
    public static void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        // 先递归访问左子树
        postOrder(root.left);
        // 再递归访问右子树
        postOrder(root.right);
        // 最后访问根节点
        System.out.print(root.val + " ");
    }

    /**
     * 传入一颗二叉树的根节点，就能统计出当前二叉树中一共有多少个节点，返回节点数
     * 此时的访问就不再是输出节点值，而是计数器 + 1操作
     * @param root
     * @return 当前二叉树的节点个数
     */
    public static int getNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + getNodes(root.left) + getNodes(root.right);
    }

    /**
     * 使用层序遍历来统计当前树中的节点个数
     * @param root
     * @return
     */
    public static int getNodesNonRecursion(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int size = 0;
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            // 此处的访问操作就是统计节点个数
            size ++;
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
        return size;
    }


    /**
     * 传入一颗二叉树的根节点，就能统计出当前二叉树的叶子结点个数
     * @param root
     * @return
     */
    public static int getLeafNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        return getLeafNodes(root.left) + getLeafNodes(root.right);
    }

    /**
     * 使用层序遍历来统计叶子结点的个数
     * @param root
     * @return
     */
    public static int getLeafNodesNonRecursion(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int size = 0;
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            // 只有当前cur是叶子节点时才计数器 + 1
            if (cur.left == null && cur.right == null) {
                size ++;
                continue;
            }
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
        return size;
    }

    /**
     * 判断当前以root为根节点的二叉树中是否包含指定元素val，
     * 若存在返回true，不存在返回false
     * @param val
     * @return
     */
    public static boolean contains(TreeNode root,char val) {
        if (root == null) {
            return false;
        }
        if (root.val == val) {
            return true;
        }
        // 二叉树不为空且根节点值不是val，在子树中继续寻找
        return contains(root.left,val) || contains(root.right,val);
    }

    /**
     * 传入一个以root为根节点的二叉树，就能求出该树的高度
     * @param root
     * @return
     */
    public static int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + Math.max(height(root.left),height(root.right));
    }

    /**
     * 求出以root为根节点的二叉树第k层的节点个数
     * @param root
     * @param k
     * @return
     */
    public static int getKLevelNodes(TreeNode root,int k) {
        if (root == null || k <= 0) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        return getKLevelNodes(root.left,k - 1) + getKLevelNodes(root.right, k - 1);
    }

    public static void main(String[] args) {
        TreeNode root = build();
//        System.out.println("前序遍历的结果为:");
//        preOrder(root);
//        System.out.println();
//        System.out.println("中序遍历的结果为:");
//        inOrder(root);
//        System.out.println();
//        System.out.println("后序遍历的结果为:");
//        postOrder(root);
//        System.out.println("当前二叉树一共有:"+getNodes(root)+"个节点数");
//        System.out.println("当前二叉树一共有:"+getNodesNonRecursion(root)+"个节点数");
        System.out.println("当前二叉树一共有:"+getLeafNodes(root)+"个叶子节点数");
        System.out.println("当前二叉树一共有:"+getLeafNodesNonRecursion(root)+"个叶子节点数");
//        System.out.println(contains(root,'E'));
//        System.out.println(contains(root,'P'));
//        System.out.println("当前二叉树的高度为:"+height(root));
//        System.out.println("当前二叉树第3层的节点个数为:"+getKLevelNodes(root,3));
    }
}